home *** CD-ROM | disk | FTP | other *** search
/ Technotools / Technotools (Chestnut CD-ROM)(1993).ISO / lang_c / cug172 / base.c next >
C/C++ Source or Header  |  1986-02-05  |  8KB  |  255 lines
  1. /*
  2.   HEADER: CUG     nnn.nn;
  3.   TITLE:     LEX - A Lexical Analyser Generator
  4.   VERSION:     1.0 for IBM-PC
  5.   DATE:      Jan 30, 1985
  6.   DESCRIPTION:     A Lexical Analyser Generator. From UNIX
  7.   KEYWORDS:     Lexical Analyser Generator YACC C PREP
  8.   SYSTEM:     IBM-PC and Compatiables
  9.   FILENAME:      BASE.C
  10.   WARNINGS:     This program is not for the casual user. It will
  11.          be useful primarily to expert developers.
  12.   CRC:         N/A
  13.   SEE-ALSO:     YACC and PREP
  14.   AUTHORS:     Scott Guthery 11100 leafwood lane Austin, TX 78750
  15.   COMPILERS:     DESMET-C
  16.   REFERENCES:     UNIX Systems Manuals
  17. */
  18. /*
  19.  * Copyright (c) 1978 Charles H. Forsyth
  20.  *
  21.  * Modified 02-Dec-80 Bob Denny -- Conditionalize debug code to reduce size
  22.  * More     29-May-81 Bob Denny -- RSX overlaying
  23.  * More     19-Mar-82 Bob Denny -- New C library & compiler
  24.  * More     28-Aug-82 Bob Denny -- Reference "a" to shut up compiler
  25.  * More        20-Nov-83 Scott Guthery -- Adapted for IBM PC & DeSmet C
  26.  */
  27.  
  28. /*
  29.  * lex -- find and set base values for `move' vector
  30.  */
  31. #include <stdio.h>
  32. #include "lexlex.h"
  33.  
  34. extern struct set *chase();
  35.  
  36. /*
  37.  * Choose the best default state for `st'.
  38.  * Only states previous to the current state are considered,
  39.  * as these are guaranteed to exist.
  40.  */
  41. struct dfa *
  42. defalt(st, xsep)
  43. struct dfa *st;
  44. struct xset **xsep;
  45. {
  46.         register struct dfa *dp;
  47.         register unsigned minv, u;
  48.         struct dfa *def;
  49.         struct xset *xse;
  50.         int i;
  51.  
  52.         xse = *xsep;
  53.         if ((i = xse-sets)==0)
  54.                 return(NULL);
  55. #ifdef DEBUG
  56.         if (lldebug>1)
  57.                 fprintf(stderr, "State %d, default:\n", st-dfa);
  58. #endif
  59.         minv = -1;
  60.         def = NULL;
  61.         for (dp = dfa; dp < st; dp++) {
  62.                 u = compat(st, dp, xse);
  63. #ifdef DEBUG
  64.                 if (lldebug > 1)
  65.                         fprintf(stderr, "\t%d rates %d\n", dp-dfa, u);
  66. #endif
  67.                 if (u < minv) {
  68.                         def = dp;
  69.                         minv = u;
  70.                 }
  71.         }
  72.         if (minv == -1 || 10*(i-(int)minv) < i)
  73.                 def = NULL;
  74. #ifdef DEBUG
  75.         if (lldebug>1 && def)
  76.                 fprintf(stderr, "\t%d chosen\n", def-dfa);
  77. #endif
  78.  
  79.         if (def)
  80.                 resolve(st, def, xsep);
  81.         return(def);
  82. }
  83.  
  84. /*
  85.  * State `b' is compatible with, and hence a suitable default state
  86.  * for state `a', if its transitions agree with
  87.  * those of `a', except those for which `a' has transitions to the
  88.  * (alleged) default. Circularity of the default
  89.  * relation is also not allowed. If the state `b' has at least
  90.  * twice as many transitions as `a', it is not even worth considering.
  91.  */
  92. compat(a, b, xse)
  93. struct dfa *a, *b;
  94. struct xset *xse;
  95. {
  96.         register struct dfa *dp;
  97.         struct xset *xs;
  98.         register nt;
  99.  
  100.         if (a==b || b->df_ntrans >= a->df_ntrans*2)
  101.                 return(-1);
  102.         for (dp = b; dp; dp = dp->df_default)
  103.                 if (dp == a)
  104.                         return(-1);
  105.         nt = b->df_ntrans + a->df_ntrans;
  106.         for (xs = sets; xs < xse; xs++)
  107.                 if (chase(b, xs->x_char) == xs->x_set)
  108.                         nt -= 2;
  109.         return(nt);
  110. }
  111.  
  112. struct set *
  113. chase(st, c)
  114. register struct dfa *st;
  115. register c;
  116. {
  117.         register struct move *dp;
  118.  
  119.         c &= 0377;
  120.         while ((dp = st->df_base) != NULL &&
  121.                ((dp += c) >= st->df_max || dp->m_check != st))
  122.                 if ((st = st->df_default) == NULL)
  123.                         return(NULL);
  124.         if (dp)
  125.                 dp = dp->m_next;
  126.         return(dp);
  127. }
  128.  
  129. /*
  130.  * set `sets' to indicate those characters on which the state `a'
  131.  * and its default agree and those characters on which `a'
  132.  * should go to `error' (as the default accepts it, but `a' does not).
  133.  */
  134. resolve(a, def, xsep)
  135. struct dfa *a, *def;
  136. struct xset **xsep;
  137. {
  138.         register struct move *dp;
  139.         register c, i;
  140.         struct xset *xs, *xse;
  141.  
  142.         a = a;                          /* Quiet compiler the easy way */
  143.  
  144.         xse = *xsep;
  145.         i = xse-sets;
  146.         for (xs = sets; xs < xse; xs++)
  147.                 xs->x_defsame = 0;
  148.         for (; def; def = def->df_default)
  149.         for (dp = def->df_base; dp < def->df_max; dp++)
  150.                 if (dp->m_check == def) {
  151.                         c = dp - def->df_base;
  152.                         for (xs = sets; xs < xse; xs++)
  153.                                 if (c==(xs->x_char&0377)) {
  154.                                         if (xs->x_set==dp->m_next) {
  155.                                                 xs->x_defsame++;
  156.                                                 i--;
  157.                                         }
  158.                                         break;
  159.                                 }
  160.                         if (xs >= xse) {
  161.                                 xs->x_defsame = 0;
  162.                                 xs->x_char = c;
  163.                                 xs->x_set = NULL;
  164.                                 i++;
  165.                                 xse++;
  166.                         }
  167.                 }
  168.         *xsep = xse;
  169.         return(i);
  170. }
  171.  
  172. /*
  173.  * Choose a base in `move' for the current state.
  174.  * The transitions of that state are in the vector `sets'.
  175.  */
  176. struct move *
  177. stbase(xse)
  178. struct xset *xse;
  179. {
  180.         register a;
  181.         register struct move *base;
  182.         register conflicts;
  183.         struct xset *xs;
  184.  
  185.         if (xse==sets)
  186.                 return(NULL);
  187.         base = move;
  188.         do {
  189.                 if (base-move >= NNEXT) {
  190.                         error("No space in `move' (stbase)");
  191.  
  192. #ifdef DEBUG
  193.                         if (lldebug>1)
  194.                                 dfaprint();
  195. #endif
  196.                         exit(1);
  197.                 }
  198.                 conflicts = 0;
  199.                 for (xs = sets; xs < xse; xs++) {
  200.                         a = xs->x_char&0377;
  201.                         if (xs->x_defsame==0 &&
  202.                             (base+a>=move+NNEXT || base[a].m_check!=NULL)) {
  203.                                 conflicts++;
  204.                                 base++;
  205.                                 break;
  206.                         }
  207.                 }
  208.         } while (conflicts);
  209.         return(base);
  210. }
  211.  
  212. /*
  213.  * Given a state, its `base' value in `move',
  214.  * and the set of transitions in `sets' (ending near `xse'),
  215.  * set the `move' values.
  216.  */
  217. setbase(st, base, xse)
  218. struct dfa *st;
  219. register struct move *base;
  220. struct xset *xse;
  221. {
  222.         register struct move *dp;
  223.         register struct xset *xs;
  224.         struct move *maxdp;
  225.  
  226.         st->df_base = base;
  227.         st->df_max = base;
  228. #ifdef DEBUG
  229.         if (lldebug>1)
  230.                 fprintf(stderr, "Setbase: state %d\n", st-dfa);
  231.         if (lldebug>1 && base==0)
  232.                 fprintf(stderr, "\tno base\n");
  233. #endif
  234.         if (base==NULL)
  235.                 return;
  236.         maxdp = base;
  237.         for (xs = sets; xs < xse; xs++)
  238.                 if (xs->x_defsame==0) {
  239.                         dp = base + (int)xs->x_char;
  240.                         if (dp > maxdp)
  241.                                 maxdp = dp;
  242.                         dp->m_next = xs->x_set;
  243.                         dp->m_check = st;
  244.                         if (dp-move > llnxtmax)
  245.                                 llnxtmax = dp-move;
  246. #ifdef DEBUG
  247.                         if (lldebug>1)
  248.                         fprintf(stderr, "\t%c nets %d\n",
  249.                                 xs->x_char&0377, dp-move);
  250. #endif
  251.                 }
  252.  
  253.         st->df_max = maxdp+1;
  254. }
  255.